W10. Сингулярное разложение (Singular Value Decomposition, SVD)

1. Краткое содержание

1.1 Введение и мотивация

Разложение по собственным векторам (eigenvalue decomposition) — один из самых мощных инструментов линейной алгебры, но у него есть существенное ограничение: оно применимо только к квадратным матрицам и, к тому же, лишь к диагонализуемым. Многие важные в приложениях матрицы — «высокие» матрицы данных, «широкие» системные матрицы, прямоугольные преобразования — вообще не укладываются в эту схему. Нужна универсальная факторизация, которая существует для любой матрицы любого размера и любого ранга.

Есть и второе, более тонкое ограничение. Даже для симметричных матриц разложение по собственным векторам даёт один ортонормированный базис собственных векторов, который одновременно диагонализует матрицу и в области определения, и в области значений: для симметричной \(A = PDP^{-1}\) пространства «входа» и «выхода» совпадают. Для произвольной прямоугольной матрицы \(A \in \mathbb{R}^{m \times n}\) область определения — \(\mathbb{R}^n\), а область значений — \(\mathbb{R}^m\): это два разных пространства. Нужны два ортонормированных базиса — один в \(\mathbb{R}^n\) и один в \(\mathbb{R}^m\).

Спектральная теорема (Spectral Theorem) утверждает, что у любой вещественной симметричной матрицы \(S = S^T\) есть разложение \(S = Q\Lambda Q^T\) с ортогональной \(Q\). Это сильный и красивый результат, но он опирается на симметрию — довольно жёсткое предположение. Хочется иметь столь же «аккуратную» картину для произвольных матриц.

Сингулярное разложение (Singular Value Decomposition, SVD) — как раз такой универсальный приём. Любую вещественную матрицу \(A \in \mathbb{R}^{m \times n}\) можно представить произведением трёх матриц — ортогональной, «диагональной» (в прямоугольном смысле) и снова ортогональной — и этим полностью описать геометрию и алгебру \(A\) там, где спектральное разложение собственных векторов уже не работает. У каждой вещественной матрицы есть SVD; никаких условий на форму, ранг или симметрию не требуется.

1.2 Основы SVD

Базовый факт формулируется так:

Теорема (существование SVD). Для любой матрицы \(A \in \mathbb{R}^{m \times n}\) ранга \(r\) существуют ортогональные матрицы \(U \in \mathbb{R}^{m \times m}\), \(V \in \mathbb{R}^{n \times n}\) и матрица \(\Sigma \in \mathbb{R}^{m \times n}\) такие, что:

\[A = U \Sigma V^T\]

Столбцы \(U\) называют левыми сингулярными векторами (left singular vectors) матрицы \(A\); они образуют ортонормированный базис в \(\mathbb{R}^m\). Столбцы \(V\) — правые сингулярные векторы (right singular vectors); они образуют ортонормированный базис в \(\mathbb{R}^n\). Матрица \(\Sigma\) диагональна в том смысле, что вне главной диагонали стоят нули; на диагонали стоят неотрицательные вещественные числа \(\sigma_1 \geq \sigma_2 \geq \cdots \geq \sigma_r > 0\). Эти диагональные элементы — сингулярные числа (singular values) матрицы \(A\).

Геометрически: \(V^T\) поворачивает (или отражает) векторы в \(\mathbb{R}^n\), выравнивая их с осями координат; \(\Sigma\) растягивает каждую ось на соответствующее сингулярное число (и отображает \(\mathbb{R}^n\) в \(\mathbb{R}^m\)); затем \(U\) действует в \(\mathbb{R}^m\) как поворот/отражение, давая образ. Любое линейное отображение раскладывается в такую цепочку: поворот — растяжение — поворот.

1.2.1 Форма \(\Sigma\) для разных размеров матрицы

Матрица \(\Sigma\) имеет тот же размер, что и \(A\), то есть \(\Sigma \in \mathbb{R}^{m \times n}\), а вне главной диагонали все элементы нулевые. На диагонали стоят сингулярные числа.

• «Высокая» матрица (\(m > n\)): \(\Sigma\) выглядит как диагональный блок \(n \times n\), «под которым» лежит нулевой блок \((m - n) \times n\). Ненулевых сингулярных чисел не больше \(n\).
• «Широкая» матрица (\(m < n\)): сверху диагональный блок \(m \times m\), справа — нулевой блок \(m \times (n - m)\). Ненулевых сингулярных чисел не больше \(m\).
• Квадратная матрица (\(m = n\)): \(\Sigma\) — диагональная матрица \(n \times n\).

Во всех случаях ненулевых сингулярных чисел не больше \(r = \min(m, n)\), а ранг \(A\) совпадает с числом строго положительных сингулярных чисел.

1.3 Свойства сингулярных чисел

Сингулярные числа обладают рядом свойств, из‑за которых их удобно считать мерой «размера» и «сложности» матрицы.

Неотрицательность и порядок: по соглашению сингулярные числа нумеруют в невозрастающем порядке: \(\sigma_1 \geq \sigma_2 \geq \cdots \geq \sigma_r > 0 = \sigma_{r+1} = \cdots\). Они всегда вещественны и \(\geq 0\), какими бы ни были элементы \(A\).

Ранг: ранг \(A\) равен числу ненулевых сингулярных чисел. Это даёт практический способ найти ранг по SVD.

Связь с нормами матрицы: наибольшее сингулярное число \(\sigma_1\) совпадает с операторной (спектральной) нормой \(\|A\|_2 = \max_{\|x\|=1} \|Ax\|\). Норма Фробениуса (Frobenius norm) удовлетворяет \(\|A\|_F = \sqrt{\sigma_1^2 + \sigma_2^2 + \cdots + \sigma_r^2}\).

Единственность: сами сингулярные числа \(A\) однозначны (зависят только от \(A\), а не от выбора разложения). Сингулярные векторы при повторяющихся сингулярных числах, наоборот, не единственны.

1.4 Вычисление SVD

Практические алгоритмы опираются на тесную связь между \(A\) и симметричными матрицами \(A^TA\) и \(AA^T\).

1.4.1 Связь с \(A^TA\) и \(AA^T\)

Пусть \(A = U\Sigma V^T\). Тогда:

\[A^TA = (U\Sigma V^T)^T(U\Sigma V^T) = V\Sigma^T U^T U \Sigma V^T = V(\Sigma^T\Sigma)V^T\]

Это и есть спектральное разложение \(A^TA\): столбцы \(V\) — собственные векторы \(A^TA\), а собственные значения \(A^TA\) равны \(\sigma_i^2\) (квадратам сингулярных чисел).

Аналогично:

\[AA^T = U\Sigma V^T (U\Sigma V^T)^T = U\Sigma V^T V \Sigma^T U^T = U(\Sigma\Sigma^T)U^T\]

Значит, столбцы \(U\) — собственные векторы \(AA^T\), а собственные значения \(AA^T\) снова \(\sigma_i^2\).

Ключевые соотношения:

\[A^T A\, \mathbf{v}_i = \sigma_i^2\, \mathbf{v}_i, \qquad \mathbf{u}_i = \frac{A\mathbf{v}_i}{\sigma_i}\]

Правые сингулярные векторы \(\mathbf{v}_i\) — это единичные собственные векторы \(A^TA\); левые \(\mathbf{u}_i\) при \(i \leq r\) получают, применяя \(A\) к \(\mathbf{v}_i\) и нормируя. Остальные столбцы \(U\) (когда \(r < m\)) дополняют до ортонормированного базиса, например взяв ортонормированный базис в ядре \(A^T\) (null space).

1.4.2 Пошаговый алгоритм

Дана \(A \in \mathbb{R}^{m \times n}\):

1. Вычислить \(A^TA \in \mathbb{R}^{n \times n}\). Матрица симметрична и положительно полуопределённа (positive semi-definite, PSD).
2. Найти собственные значения \(\lambda_1 \geq \lambda_2 \geq \cdots \geq \lambda_n \geq 0\) матрицы \(A^TA\) (они \(\geq 0\), так как \(A^TA\) — PSD).
3. Сингулярные числа: \(\sigma_i = \sqrt{\lambda_i}\) для \(i = 1, \ldots, r\), где \(r\) — число положительных собственных значений.
4. Единичные собственные векторы \(A^TA\) как столбцы \(\mathbf{v}_1, \ldots, \mathbf{v}_n\) матрицы \(V\).
5. Левые сингулярные векторы: \(\mathbf{u}_i = \dfrac{A\mathbf{v}_i}{\sigma_i}\) для \(i = 1, \ldots, r\).
6. Дополнить \(U\): семейство \(\{\mathbf{u}_1, \ldots, \mathbf{u}_r\}\) достроить до полного ортонормированного базиса в \(\mathbb{R}^m\) (часто через ядро \(A^T\)).
7. Собрать \(U\), \(\Sigma\), \(V\) и проверить \(A = U\Sigma V^T\).

1.4.3 Особые случаи

Матрица ранга 1: если \(\text{rank}(A)=1\), то \(A = \mathbf{u}\mathbf{v}^T\) (внешнее произведение двух векторов с масштабом). Единственное ненулевое сингулярное число связано с нормой строки (или столбца); остальные сингулярные числа нулевые.

Симметричная положительно полуопределённая матрица: если \(A = A^T\) и все собственные значения \(\lambda_i \geq 0\), то SVD совпадает со спектральным разложением: \(\sigma_i = \lambda_i\) и \(U = V = Q\) (матрица собственных векторов). Вычисление SVD в этом случае — то же самое, что диагонализация \(A\).

1.5 Алгебраические следствия для SVD

Из \(A = U\Sigma V^T\) сразу читается SVD «родственных» матриц:

Транспонирование: \(A^T = V\Sigma^T U^T\). Матрицы \(U\) и \(V\) просто меняются ролями. Сингулярные числа те же — у \(A\) и \(A^T\) они всегда совпадают.

Обратная (квадратная невырожденная): если \(A\) размера \(n \times n\) обратима, то \[A^{-1} = V\Sigma^{-1}U^T, \quad \text{где } \Sigma^{-1} = \text{diag}(1/\sigma_1, \ldots, 1/\sigma_n)\]

Ведь \((V\Sigma^{-1}U^T)(U\Sigma V^T) = V\Sigma^{-1}\Sigma V^T = VV^T = I\).

Умножение на скаляр: для любого скаляра \(c\) \[(cA) = U(c\Sigma)V^T\]

Сингулярные числа \(cA\) равны \(|c|\sigma_1, |c|\sigma_2, \ldots\). Матрицы \(U\) и \(V\) от масштаба не зависят. Если \(c < 0\), сами сингулярные числа остаются \(\geq 0\): знак можно «поглотить» поворотом в \(U\) или \(V\).

1.6 Четыре фундаментальных подпространства через SVD

SVD даёт полное и наглядное описание четырёх фундаментальных подпространств (four fundamental subspaces) матрицы — одно из главных приложений разложения.

Напомним: для \(A \in \mathbb{R}^{m \times n}\) ранга \(r\):

• Столбцовое пространство (column space) \(C(A) \subseteq \mathbb{R}^m\) имеет размерность \(r\).
• Левое ядро (left null space) \(N(A^T) \subseteq \mathbb{R}^m\) имеет размерность \(m - r\).
• Строчное пространство (row space) \(C(A^T) \subseteq \mathbb{R}^n\) имеет размерность \(r\).
• Ядро (null space) \(N(A) \subseteq \mathbb{R}^n\) имеет размерность \(n - r\).

Из SVD \(A = U\Sigma V^T\) эти подпространства читаются напрямую:

• \(C(A)\): линейная оболочка первых \(r\) столбцов \(U\): \(\{\mathbf{u}_1, \ldots, \mathbf{u}_r\}\).
• \(N(A^T)\): линейная оболочка последних \(m - r\) столбцов \(U\): \(\{\mathbf{u}_{r+1}, \ldots, \mathbf{u}_m\}\).
• \(C(A^T)\): линейная оболочка первых \(r\) столбцов \(V\): \(\{\mathbf{v}_1, \ldots, \mathbf{v}_r\}\).
• \(N(A)\): линейная оболочка последних \(n - r\) столбцов \(V\): \(\{\mathbf{v}_{r+1}, \ldots, \mathbf{v}_n\}\).

Это и есть фундаментальная теорема линейной алгебры (Fundamental Theorem of Linear Algebra): четыре подпространства разбиваются на две ортогональные пары — \(C(A) \perp N(A^T)\) в \(\mathbb{R}^m\) и \(C(A^T) \perp N(A)\) в \(\mathbb{R}^n\). Столбцы \(U\) образуют ортонормированный базис в \(\mathbb{R}^m\), согласованный с \(C(A)\) и \(N(A^T)\); столбцы \(V\) — ортонормированный базис в \(\mathbb{R}^n\), согласованный с \(C(A^T)\) и \(N(A)\).

Почему так: при \(i \leq r\) имеем \(A\mathbf{v}_i = \sigma_i \mathbf{u}_i\), поэтому первые \(r\) столбцов \(V\) переходят в \(r\) независимых векторов из \(C(A)\). При \(i > r\) выполнено \(A\mathbf{v}_i = \mathbf{0}\), то есть \(\mathbf{v}_{r+1}, \ldots, \mathbf{v}_n\) лежат в \(N(A)\).

1.7 SVD как сумма матриц ранга 1

Развёртывание произведения \(A = U\Sigma V^T\) по столбцам даёт удобное представление:

\[A = \sum_{i=1}^{r} \sigma_i\, \mathbf{u}_i \mathbf{v}_i^T\]

Каждое слагаемое \(\sigma_i \mathbf{u}_i \mathbf{v}_i^T\) — матрица ранга 1 (rank-1 matrix): внешнее произведение двух векторов, умноженное на \(i\)-е сингулярное число. Так «информация» в \(A\) упорядочена по важности: первое слагаемое \(\sigma_1 \mathbf{u}_1 \mathbf{v}_1^T\) вносит наибольший вклад (у \(\sigma_1\) наибольшая величина), дальше вклад слагаемых убывает.

Эта иерархия по вкладу (information hierarchy) — ключ к низкоранговой аппроксимации (low-rank approximation): отбросив малые слагаемые, получают матрицу, близкую к \(A\), но с гораздо меньшим рангом — её проще хранить и обрабатывать.

1.8 Приложения: низкий ранг, сжатие изображений, шумоподавление

1.8.1 Норма Фробениуса и энергия

Норма Фробениуса (Frobenius norm) матрицы \(A\):

\[\|A\|_F = \sqrt{\sum_{i,j} a_{ij}^2} = \sqrt{\sigma_1^2 + \sigma_2^2 + \cdots + \sigma_r^2}\]

Второе равенство — прямое следствие SVD. Квадрат нормы Фробениуса удобно трактовать как полную энергию матрицы. Доля энергии, которую дают первые \(k\) сингулярных чисел:

\[\text{доля энергии} = \frac{\sigma_1^2 + \sigma_2^2 + \cdots + \sigma_k^2}{\sigma_1^2 + \sigma_2^2 + \cdots + \sigma_r^2}\]

Эта величина важна при выборе \(k\) в низкоранговой аппроксимации.

1.8.2 Теорема Эккарта — Янга (Eckart–Young)

Аппроксимация ранга \(k\) (rank-\(k\) approximation) для \(A\):

\[A_k = \sum_{i=1}^{k} \sigma_i\, \mathbf{u}_i \mathbf{v}_i^T\]

Это усечённая сумма: оставляют только \(k\) старших слагаемых в разложении по ранг-1 матрицам.

Теорема (Eckart–Young, 1936). Среди всех матриц \(B\) ранга не выше \(k\) ближайшая к \(A\) по норме Фробениуса (и по спектральной норме) — это \(A_k\):

\[\|A - A_k\|_F = \min_{\text{rank}(B) \leq k} \|A - B\|_F = \sqrt{\sigma_{k+1}^2 + \sigma_{k+2}^2 + \cdots + \sigma_r^2}\]

То есть усечение SVD до \(k\) сингулярных чисел оптимально: другой матрицы ранга \(\leq k\), ближе в \(\|\cdot\|_F\), не существует. Ошибка аппроксимации — «энергия» отброшенных сингулярных чисел.

1.8.3 Сжатие изображений

Полутоновое изображение размера \(m \times n\) пикселей естественно хранить как матрицу \(A \in \mathbb{R}^{m \times n}\). Полная матрица — это \(mn\) чисел. В ранг-\(k\) аппроксимации SVD хранят:

• \(k\) сингулярных чисел: \(k\) чисел;
• \(k\) левых сингулярных векторов: \(mk\) чисел;
• \(k\) правых сингулярных векторов: \(nk\) чисел.

Итого: \(k(m + n + 1)\) чисел против \(mn\) для полной матрицы. Коэффициент сжатия (compression ratio) — \(k(m + n + 1) / (mn)\).

При небольшом \(k\) можно сильно сократить объём памяти, сохранив основную структуру картинки: у «естественных» изображений сингулярные числа часто быстро убывают, и большая часть энергии сосредоточена в первых нескольких.

1.8.4 Шумоподавление и PCA

Помимо сжатия, SVD — ядро метода главных компонент (Principal Component Analysis, PCA): правые сингулярные векторы \(\mathbf{v}_i\) (то же самое, что собственные векторы \(A^TA\)) — главные компоненты (principal components), направления наибольшей дисперсии данных. Проекция на первые \(k\) компонент выделяет наиболее информативные признаки.

В шумоподавлении (denoising) шумную матрицу моделируют как \(A = A_{\text{signal}} + A_{\text{noise}}\), где сигнал низкоранговый, а шум «размазан» по всем сингулярным числам. Усечение SVD по нескольким старшим сингулярным числам подавляет шум, сохраняя доминирующую структуру сигнала.

---

2. Определения

• Сингулярное разложение (Singular Value Decomposition, SVD): представление \(A = U\Sigma V^T\) для любой вещественной \(A \in \mathbb{R}^{m \times n}\), где \(U \in \mathbb{R}^{m \times m}\) и \(V \in \mathbb{R}^{n \times n}\) ортогональны, а \(\Sigma \in \mathbb{R}^{m \times n}\) имеет неотрицательные элементы только на главной диагонали.
• Левые сингулярные векторы (left singular vectors): столбцы \(\mathbf{u}_1, \ldots, \mathbf{u}_m\) матрицы \(U\) в SVD; ортонормированный базис в \(\mathbb{R}^m\).
• Правые сингулярные векторы (right singular vectors): столбцы \(\mathbf{v}_1, \ldots, \mathbf{v}_n\) матрицы \(V\) в SVD; ортонормированный базис в \(\mathbb{R}^n\).
• Сингулярные числа (singular values): неотрицательные диагональные элементы \(\sigma_1 \geq \sigma_2 \geq \cdots \geq \sigma_r > 0\) матрицы \(\Sigma\); выполняется \(\sigma_i = \sqrt{\lambda_i(A^TA)}\).
• Ранг по SVD: \(\text{rank}(A)\) равен числу строго положительных сингулярных чисел.
• Столбцовое пространство \(C(A)\) (column space): подпространство в \(\mathbb{R}^m\), натянутое на столбцы \(A\); в SVD — \(\text{span}\{\mathbf{u}_1, \ldots, \mathbf{u}_r\}\).
• Ядро \(N(A)\) (null space): подпространство в \(\mathbb{R}^n\) из всех \(\mathbf{x}\) с \(A\mathbf{x} = \mathbf{0}\); в SVD — \(\text{span}\{\mathbf{v}_{r+1}, \ldots, \mathbf{v}_n\}\).
• Строчное пространство \(C(A^T)\) (row space): столбцовое пространство \(A^T\), то же, что линейная оболочка строк \(A\) в \(\mathbb{R}^n\); в SVD — \(\text{span}\{\mathbf{v}_1, \ldots, \mathbf{v}_r\}\).
• Левое ядро \(N(A^T)\) (left null space): ядро \(A^T\) как подпространство в \(\mathbb{R}^m\); в SVD — \(\text{span}\{\mathbf{u}_{r+1}, \ldots, \mathbf{u}_m\}\).
• Норма Фробениуса (Frobenius norm): \(\|A\|_F = \sqrt{\sum_{i,j} a_{ij}^2} = \sqrt{\sum_i \sigma_i^2}\); мера «полного размера» матрицы.
• Аппроксимация ранга \(k\) (rank-\(k\) approximation): \(A_k = \sum_{i=1}^k \sigma_i \mathbf{u}_i \mathbf{v}_i^T\) — усечённое разложение по \(k\) старшим сингулярным числам.
• Теорема Эккарта — Янга (Eckart–Young theorem): \(A_k\) — ближайшая к \(A\) матрица ранга \(\leq k\) и в норме Фробениуса, и в спектральной; \(\|A - A_k\|_F = \sqrt{\sum_{i > k} \sigma_i^2}\).
• Внешнее произведение (outer product), матрица ранга 1: матрица \(\mathbf{u}\mathbf{v}^T \in \mathbb{R}^{m \times n}\) для столбцов \(\mathbf{u} \in \mathbb{R}^m\), \(\mathbf{v} \in \mathbb{R}^n\); её ранг не больше 1.

---

3. Формулы

• Разложение SVD: \(A = U\Sigma V^T\), где \(U^TU = I_m\), \(V^TV = I_n\), \(\Sigma_{ij} = 0\) при \(i \neq j\), \(\Sigma_{ii} = \sigma_i \geq 0\).
• Правые сингулярные векторы из \(A^TA\): \(A^T A\, \mathbf{v}_i = \sigma_i^2\, \mathbf{v}_i\) (собственные векторы \(A^TA\)).
• Левые из правых: \(\mathbf{u}_i = \dfrac{A\mathbf{v}_i}{\sigma_i}\) при \(i = 1, \ldots, r\).
• SVD транспонированной: \(A^T = V\Sigma^T U^T\).
• SVD обратной (квадратная, обратимая): \(A^{-1} = V\Sigma^{-1}U^T\).
• SVD произведения на скаляр: \(cA = U(c\Sigma)V^T\); сингулярные числа \(cA\) равны \(|c|\sigma_i\).
• Разложение в сумму ранг-1: \(A = \displaystyle\sum_{i=1}^{r} \sigma_i\, \mathbf{u}_i \mathbf{v}_i^T\).
• Лучшая аппроксимация ранга \(k\) (Eckart–Young): \(A_k = \displaystyle\sum_{i=1}^{k} \sigma_i\, \mathbf{u}_i \mathbf{v}_i^T\).
• Ошибка по Фробениусу: \(\|A - A_k\|_F^2 = \sigma_{k+1}^2 + \sigma_{k+2}^2 + \cdots + \sigma_r^2\).
• Норма Фробениуса через сингулярные числа: \(\|A\|_F = \sqrt{\sigma_1^2 + \sigma_2^2 + \cdots + \sigma_r^2}\).
• Память для ранг-\(k\) SVD: \(k(m + n + 1)\) чисел.
• Доля энергии первых \(k\) сингулярных чисел: \(\dfrac{\displaystyle\sum_{i=1}^{k} \sigma_i^2}{\displaystyle\sum_{i=1}^{r} \sigma_i^2}\).

---

4. Примеры

4.1 Вычислить \(A^TA\), сингулярные числа и ранг (Лаба 8, Задание 1)

Пусть \(A = \begin{bmatrix} 3 & 0 \\ 4 & 0 \end{bmatrix}\). Найдите \(A^TA\), все сингулярные числа, ранг и дайте геометрическую интерпретацию действия \(A\).

Нажмите, чтобы увидеть решение

Ключевая идея: вычисляем \(A^TA\), находим её собственные значения, извлекаем корни — это сингулярные числа, затем интерпретируем геометрию. Нулевое сингулярное число означает вырождение ранга и «схлопывание» образа.

Шаг 1 — матрица \(A^TA\).

\[A^TA = \begin{bmatrix} 3 & 4 \\ 0 & 0 \end{bmatrix}\begin{bmatrix} 3 & 0 \\ 4 & 0 \end{bmatrix} = \begin{bmatrix} 3\cdot3+4\cdot4 & 3\cdot0+4\cdot0 \\ 0\cdot3+0\cdot4 & 0\cdot0+0\cdot0 \end{bmatrix} = \begin{bmatrix} 25 & 0 \\ 0 & 0 \end{bmatrix}\]

Шаг 2 — собственные значения \(A^TA\).

Так как \(A^TA = \text{diag}(25, 0)\) диагональна, собственные значения читаются сразу: \[\lambda_1 = 25, \qquad \lambda_2 = 0\]

Шаг 3 — сингулярные числа.

\[\sigma_1 = \sqrt{25} = 5, \qquad \sigma_2 = \sqrt{0} = 0\]

Ранг равен числу строго положительных сингулярных чисел: \(\text{rank}(A) = 1\).

Шаг 4 — геометрия.

При ранге \(1\) матрица \(A\) отображает всю плоскость \(\mathbb{R}^2\) на одну прямую в \(\mathbb{R}^2\). Явно: \(A\begin{bmatrix}x\\y\end{bmatrix} = x\begin{bmatrix}3\\4\end{bmatrix}\), значит образ — прямая, натянутая на \((3,4)^T\), с единичным направлением \(\mathbf{u}_1 = \tfrac{1}{5}(3,4)^T\). Максимальное растяжение единичного входного вектора равно \(\sigma_1 = 5\). Окружность переходит не в эллипс, а в отрезок длины \(2\sigma_1 = 10\), потому что второе сингулярное число нулевое.

Ответ: \(A^TA = \begin{bmatrix}25&0\\0&0\end{bmatrix}\), сингулярные числа \(\sigma_1 = 5\), \(\sigma_2 = 0\), \(\text{rank}(A) = 1\). Геометрически \(A\) «сжимает» плоскость на прямую с направлением \(\tfrac{1}{5}(3,4)^T\) с коэффициентом растяжения \(5\).

4.2 Полное SVD (Лаба 8, Задание 2)

Найдите полное SVD матрицы \(A = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}\).

Нажмите, чтобы увидеть решение

Ключевая идея: стандартный алгоритм — \(A^TA\), её спектр даёт \(V\) и \(\Sigma\), затем левые векторы \(\mathbf{u}_i = A\mathbf{v}_i / \sigma_i\).

Шаг 1 — \(A^TA\).

\[A^TA = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^T\begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} = \begin{bmatrix} 1 & 1 \\ 1 & 1 \end{bmatrix}\begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} = \begin{bmatrix} 2 & 1 \\ 1 & 1 \end{bmatrix}\]

Шаг 2 — собственные значения \(A^TA\).

\[\det(A^TA - \lambda I) = (2-\lambda)(1-\lambda) - 1 = \lambda^2 - 3\lambda + 1 = 0\] \[\lambda = \frac{3 \pm \sqrt{9-4}}{2} = \frac{3 \pm \sqrt{5}}{2}\]

Итак \(\lambda_1 = \dfrac{3+\sqrt{5}}{2} \approx 2.618\) и \(\lambda_2 = \dfrac{3-\sqrt{5}}{2} \approx 0.382\).

Шаг 3 — сингулярные числа.

\[\sigma_1 = \sqrt{\frac{3+\sqrt{5}}{2}} \approx 1.618, \qquad \sigma_2 = \sqrt{\frac{3-\sqrt{5}}{2}} \approx 0.618\]

Шаг 4 — правые сингулярные векторы (столбцы \(V\)).

Для \(\lambda_1 = \dfrac{3+\sqrt{5}}{2}\): решаем \((A^TA - \lambda_1 I)\mathbf{v} = 0\).

\[\left(2 - \frac{3+\sqrt{5}}{2}\right)v_1 + v_2 = 0 \implies \frac{1-\sqrt{5}}{2}v_1 + v_2 = 0 \implies v_2 = \frac{\sqrt{5}-1}{2}v_1\]

Возьмём \(v_1\) пропорциональным \((2, \sqrt{5}-1)^T\). Норма этого вектора: \[\|(2, \sqrt{5}-1)^T\| = \sqrt{4 + (\sqrt{5}-1)^2} = \sqrt{4 + 6 - 2\sqrt{5}} = \sqrt{10-2\sqrt{5}}\]

\[\mathbf{v}_1 = \frac{1}{\sqrt{10-2\sqrt{5}}}\begin{bmatrix}2\\\sqrt{5}-1\end{bmatrix}\]

Для \(\lambda_2\): вектор \(\mathbf{v}_2\) ортогонален \(\mathbf{v}_1\):

\[\mathbf{v}_2 = \frac{1}{\sqrt{10-2\sqrt{5}}}\begin{bmatrix}1-\sqrt{5}\\2\end{bmatrix}\]

Шаг 5 — левые сингулярные векторы.

\[A\mathbf{v}_1 = \frac{1}{\sqrt{10-2\sqrt{5}}}\begin{bmatrix}1&1\\1&0\end{bmatrix}\begin{bmatrix}2\\\sqrt{5}-1\end{bmatrix} = \frac{1}{\sqrt{10-2\sqrt{5}}}\begin{bmatrix}1+\sqrt{5}\\2\end{bmatrix}\]

\[\|(1+\sqrt{5}, 2)^T\| = \sqrt{(1+\sqrt{5})^2+4} = \sqrt{10+2\sqrt{5}}\]

\[\mathbf{u}_1 = \frac{A\mathbf{v}_1}{\sigma_1} = \frac{(1+\sqrt{5}, 2)^T}{\sqrt{10+2\sqrt{5}}}\]

Аналогично, \(A\mathbf{v}_2 = \tfrac{1}{\sqrt{10-2\sqrt{5}}}(3-\sqrt{5},\, 1-\sqrt{5})^T\), откуда:

\[\mathbf{u}_2 = \frac{(3-\sqrt{5},\, 1-\sqrt{5})^T}{\sqrt{(3-\sqrt{5})^2+(1-\sqrt{5})^2}/\sigma_2\sqrt{10-2\sqrt{5}}}\]

Численно: \(\sigma_1\approx 1.618\), \(\sigma_2\approx 0.618\), \(\mathbf{v}_1\approx(0.526, 0.851)^T\), \(\mathbf{v}_2\approx(-0.851, 0.526)^T\), \(\mathbf{u}_1\approx(0.851, 0.526)^T\), \(\mathbf{u}_2\approx(-0.526, 0.851)^T\).

Ответ: \(A = U\Sigma V^T\), где \(\sigma_1 = \sqrt{(3+\sqrt{5})/2} \approx 1.618\), \(\sigma_2 = \sqrt{(3-\sqrt{5})/2} \approx 0.618\), \(V = \tfrac{1}{\sqrt{10-2\sqrt{5}}}\begin{bmatrix}2 & 1-\sqrt{5}\\\sqrt{5}-1 & 2\end{bmatrix}\), \(U = \tfrac{1}{\sqrt{10+2\sqrt{5}}}\begin{bmatrix}1+\sqrt{5} & \sqrt{5}-3\\2 & \sqrt{5}-1\end{bmatrix}\).

4.3 SVD для \(A^T\) и \(A^{-1}\); масштабирование (Лаба 8, Задание 3)

Пользуясь SVD матрицы \(A\) из задания 4.2: (а) запишите SVD для \(A^T\); (б) найдите \(A^{-1}\) из SVD; (в) как изменятся сингулярные числа, если \(A\) заменить на \(4A\)?

Нажмите, чтобы увидеть решение

Ключевая идея: формулы \(A^T = V\Sigma^T U^T\), \(A^{-1} = V\Sigma^{-1}U^T\) и \((cA) = U(c\Sigma)V^T\) позволяют сразу записать разложения для «родственных» матриц, не повторяя вычислений.

Далее \(U\), \(\Sigma\), \(V\) — из SVD \(A\) в 4.2, с \(\sigma_1 = \sqrt{(3+\sqrt{5})/2}\) и \(\sigma_2 = \sqrt{(3-\sqrt{5})/2}\).

Часть (а) — SVD для \(A^T\).

Шаг 1: формула транспонирования. Если \(A = U\Sigma V^T\), то \(A^T = (U\Sigma V^T)^T = V\Sigma^T U^T\).

Шаг 2: для квадратной \(2\times 2\) имеем \(\Sigma^T = \Sigma = \text{diag}(\sigma_1, \sigma_2)\).

Шаг 3: значит \(A^T = V \Sigma U^T\). Левые сингулярные векторы \(A^T\) — столбцы \(V\) (правые для \(A\)), правые сингулярные векторы \(A^T\) — столбцы \(U\) (левые для \(A\)). Сингулярные числа те же: \(\sigma_1\) и \(\sigma_2\).

Часть (б) — обратная матрица.

Шаг 1: обе сингулярные величины положительны (\(\sigma_1, \sigma_2 > 0\)), значит \(A\) обратима.

Шаг 2: \(A^{-1} = V\Sigma^{-1}U^T\), где \(\Sigma^{-1} = \text{diag}(1/\sigma_1,\, 1/\sigma_2)\).

\[A^{-1} = V \begin{bmatrix} 1/\sigma_1 & 0 \\ 0 & 1/\sigma_2 \end{bmatrix} U^T = V \begin{bmatrix} \sqrt{2/(3+\sqrt{5})} & 0 \\ 0 & \sqrt{2/(3-\sqrt{5})} \end{bmatrix} U^T\]

Сингулярные числа \(A^{-1}\) (в невозрастающем порядке) — \(1/\sigma_2 \geq 1/\sigma_1\), приблизительно \(1/0.618 \approx 1.618\) и \(1/1.618 \approx 0.618\).

Часть (в) — замена \(A\) на \(4A\).

Шаг 1: \(4A = U(4\Sigma)V^T\).

Шаг 2: \(U\) и \(V\) не меняются; каждое сингулярное число умножается на \(4\): \[\sigma_1(4A) = 4\sigma_1 = 4\sqrt{\frac{3+\sqrt{5}}{2}} \approx 6.472, \qquad \sigma_2(4A) = 4\sigma_2 = 4\sqrt{\frac{3-\sqrt{5}}{2}} \approx 2.472\]

Ответ: (а) \(A^T = V\Sigma U^T\) (то же \(\Sigma\), роли \(U\) и \(V\) поменялись местами, сингулярные числа те же). (б) \(A^{-1} = V\Sigma^{-1}U^T\) с сингулярными числами \(1/\sigma_2 \approx 1.618\) и \(1/\sigma_1 \approx 0.618\). (в) у \(4A\) сингулярные числа \(4\sigma_1 \approx 6.472\) и \(4\sigma_2 \approx 2.472\); \(U\) и \(V\) прежние.

4.4 Полное SVD и четыре подпространства (Лаба 8, Задание 4)

Пусть \(A = \begin{bmatrix} 1 & 2 \\ 3 & 6 \end{bmatrix}\). Найдите полное SVD и опишите все четыре фундаментальных подпространства.

Нажмите, чтобы увидеть решение

Ключевая идея: второй столбец \(A\) равен удвоенному первому, значит \(\text{rank}(A)=1\). Тогда ровно одно ненулевое сингулярное число, а четыре подпространства имеют размерности \(1\) или \(0\).

Шаг 1 — \(A^TA\).

\[A^TA = \begin{bmatrix}1&3\\2&6\end{bmatrix}\begin{bmatrix}1&2\\3&6\end{bmatrix} = \begin{bmatrix}1+9&2+18\\2+18&4+36\end{bmatrix} = \begin{bmatrix}10&20\\20&40\end{bmatrix}\]

Шаг 2 — собственные значения \(A^TA\).

\[\det\begin{bmatrix}10-\lambda&20\\20&40-\lambda\end{bmatrix} = (10-\lambda)(40-\lambda) - 400 = \lambda^2 - 50\lambda = \lambda(\lambda-50) = 0\]

Значит \(\lambda_1 = 50\), \(\lambda_2 = 0\).

Шаг 3 — сингулярные числа.

\[\sigma_1 = \sqrt{50} = 5\sqrt{2}, \qquad \sigma_2 = 0, \qquad \text{rank}(A) = 1\]

Шаг 4 — правые сингулярные векторы (столбцы \(V\)).

Для \(\lambda_1 = 50\): \((A^TA - 50I)\mathbf{v} = 0 \Rightarrow -40v_1 + 20v_2 = 0 \Rightarrow v_2 = 2v_1\). Следовательно \(\mathbf{v} \propto (1,2)^T\), после нормировки: \[\mathbf{v}_1 = \frac{1}{\sqrt{5}}\begin{bmatrix}1\\2\end{bmatrix}\]

Для \(\lambda_2 = 0\): \(\mathbf{v}_2\) ортогонален \(\mathbf{v}_1\): \[\mathbf{v}_2 = \frac{1}{\sqrt{5}}\begin{bmatrix}-2\\1\end{bmatrix}\]

\[V = \frac{1}{\sqrt{5}}\begin{bmatrix}1&-2\\2&1\end{bmatrix}\]

Шаг 5 — левые сингулярные векторы.

\[\mathbf{u}_1 = \frac{A\mathbf{v}_1}{\sigma_1} = \frac{1}{5\sqrt{2}} \cdot \frac{1}{\sqrt{5}}\begin{bmatrix}1&2\\3&6\end{bmatrix}\begin{bmatrix}1\\2\end{bmatrix} = \frac{1}{5\sqrt{10}}\begin{bmatrix}5\\15\end{bmatrix} = \frac{1}{\sqrt{10}}\begin{bmatrix}1\\3\end{bmatrix}\]

Для \(\mathbf{u}_2\): любой единичный вектор, ортогональный \(\mathbf{u}_1\) в \(\mathbb{R}^2\): \[\mathbf{u}_2 = \frac{1}{\sqrt{10}}\begin{bmatrix}-3\\1\end{bmatrix}\]

\[U = \frac{1}{\sqrt{10}}\begin{bmatrix}1&-3\\3&1\end{bmatrix}\]

Шаг 6 — собрать SVD.

\[A = U\Sigma V^T = \frac{1}{\sqrt{10}}\begin{bmatrix}1&-3\\3&1\end{bmatrix}\begin{bmatrix}5\sqrt{2}&0\\0&0\end{bmatrix}\frac{1}{\sqrt{5}}\begin{bmatrix}1&2\\-2&1\end{bmatrix}\]

Шаг 7 — четыре подпространства.

• \(C(A) = \text{span}\{\mathbf{u}_1\} = \text{span}\left\{\tfrac{1}{\sqrt{10}}(1,3)^T\right\}\)
• \(N(A^T) = \text{span}\{\mathbf{u}_2\} = \text{span}\left\{\tfrac{1}{\sqrt{10}}(-3,1)^T\right\}\)
• \(C(A^T) = \text{span}\{\mathbf{v}_1\} = \text{span}\left\{\tfrac{1}{\sqrt{5}}(1,2)^T\right\}\)
• \(N(A) = \text{span}\{\mathbf{v}_2\} = \text{span}\left\{\tfrac{1}{\sqrt{5}}(-2,1)^T\right\}\)

Ответ: \(\sigma_1 = 5\sqrt{2}\), \(\sigma_2 = 0\), \(\text{rank}(A) = 1\). \(U = \tfrac{1}{\sqrt{10}}\begin{bmatrix}1&-3\\3&1\end{bmatrix}\), \(\Sigma = \begin{bmatrix}5\sqrt{2}&0\\0&0\end{bmatrix}\), \(V = \tfrac{1}{\sqrt{5}}\begin{bmatrix}1&-2\\2&1\end{bmatrix}\).

4.5 SVD симметричной PSD-матрицы (Лаба 8, Задание 5)

Пусть \(A\) — симметричная положительно полуопределённая матрица \(3 \times 3\) с собственными значениями \(9, 4, 0\) и соответствующими ортонормированными собственными векторами \(\mathbf{q}_1, \mathbf{q}_2, \mathbf{q}_3\). Запишите SVD \(A\), укажите четыре фундаментальных подпространства и объясните, чем этот случай проще общего SVD.

Нажмите, чтобы увидеть решение

Ключевая идея: для симметричной PSD-матрицы разложение \(A = Q\Lambda Q^T\) уже и есть SVD: \(U = V = Q\), а сингулярные числа совпадают с собственными. Отдельно считать \(A^TA\) не нужно.

Шаг 1 — спектральное разложение.

Пусть \(Q = [\mathbf{q}_1\; \mathbf{q}_2\; \mathbf{q}_3]\) — матрица ортонормированных собственных векторов, \(\Lambda = \text{diag}(9, 4, 0)\). Тогда \[A = Q\Lambda Q^T = 9\,\mathbf{q}_1\mathbf{q}_1^T + 4\,\mathbf{q}_2\mathbf{q}_2^T + 0\,\mathbf{q}_3\mathbf{q}_3^T\]

Шаг 2 — запись SVD.

Сравнивая с \(A = U\Sigma V^T\), положим \(U = V = Q\) и \(\Sigma = \Lambda = \text{diag}(9, 4, 0)\).

\[A = Q\begin{bmatrix}9&0&0\\0&4&0\\0&0&0\end{bmatrix}Q^T, \qquad \sigma_1 = 9,\; \sigma_2 = 4,\; \sigma_3 = 0\]

Шаг 3 — ранг.

Ненулевых сингулярных чисел два, значит \(\text{rank}(A) = 2\).

Шаг 4 — четыре подпространства.

Так как \(A = A^T\) симметрична, \(C(A) = C(A^T)\) и \(N(A) = N(A^T)\).

• \(C(A) = C(A^T) = \text{span}\{\mathbf{q}_1, \mathbf{q}_2\}\) (размерность 2)
• \(N(A) = N(A^T) = \text{span}\{\mathbf{q}_3\}\) (размерность 1)

Шаг 5 — почему проще.

В общем алгоритме SVD нужно: (i) вычислить \(A^TA\); (ii) найти её собственные векторы для \(V\); (iii) отдельно посчитать каждое \(\mathbf{u}_i = A\mathbf{v}_i/\sigma_i\); (iv) достроить \(U\) по ядру \(A^T\). Для симметричной PSD шаги (iii)–(iv) исчезают: \(U = V = Q\). Кроме того, \(A^TA = A^2 = Q\Lambda^2 Q^T\), то есть собственные векторы \(A^TA\) совпадают с собственными векторами \(A\). SVD сводится к уже знакомому спектральному разложению.

Ответ: \(A = Q\,\text{diag}(9,4,0)\,Q^T\); \(\sigma_1 = 9\), \(\sigma_2 = 4\), \(\sigma_3 = 0\); \(\text{rank}(A) = 2\); \(C(A) = C(A^T) = \text{span}\{\mathbf{q}_1, \mathbf{q}_2\}\); \(N(A) = N(A^T) = \text{span}\{\mathbf{q}_3\}\). Упрощение: \(U = V = Q\), SVD совпадает со спектральным разложением.

4.6 Лучшие приближения рангов 1 и 2 (Лаба 8, Задание 6)

Пусть \(A = 12\,\mathbf{u}_1\mathbf{v}_1^T + 5\,\mathbf{u}_2\mathbf{v}_2^T + \mathbf{u}_3\mathbf{v}_3^T\) уже записана в виде SVD-разложения в ранг-1 слагаемые. Найдите лучшее приближение ранга 1 — \(A_1\), лучшее ранга 2 — \(A_2\), и нормы Фробениуса \(\|A - A_1\|_F\), \(\|A - A_2\|_F\).

Нажмите, чтобы увидеть решение

Ключевая идея: по теореме Eckart–Young лучшее приближение ранга \(k\) получают, оставляя \(k\) старших слагаемых в SVD-разложении. Ошибка в норме Фробениуса — корень из суммы квадратов отброшенных сингулярных чисел.

Здесь \(\sigma_1 = 12\), \(\sigma_2 = 5\), \(\sigma_3 = 1\) (невозрастающий порядок, как в SVD).

Шаг 1 — лучшее \(A_1\) ранга 1.

Оставляем только слагаемое с наибольшим сингулярным числом: \[A_1 = \sigma_1\,\mathbf{u}_1\mathbf{v}_1^T = 12\,\mathbf{u}_1\mathbf{v}_1^T\]

Шаг 2 — лучшее \(A_2\) ранга 2.

Оставляем два старших слагаемых: \[A_2 = \sigma_1\,\mathbf{u}_1\mathbf{v}_1^T + \sigma_2\,\mathbf{u}_2\mathbf{v}_2^T = 12\,\mathbf{u}_1\mathbf{v}_1^T + 5\,\mathbf{u}_2\mathbf{v}_2^T\]

Шаг 3 — \(\|A - A_1\|_F\).

По Eckart–Young отброшены \(\sigma_2 = 5\) и \(\sigma_3 = 1\): \[\|A - A_1\|_F = \sqrt{\sigma_2^2 + \sigma_3^2} = \sqrt{25 + 1} = \sqrt{26} \approx 5.10\]

Шаг 4 — \(\|A - A_2\|_F\).

Отброшено только \(\sigma_3 = 1\): \[\|A - A_2\|_F = \sqrt{\sigma_3^2} = \sqrt{1} = 1\]

Шаг 5 — смысл.

Приближение ранга 1 сохраняет \(\sigma_1^2/(\sigma_1^2+\sigma_2^2+\sigma_3^2) = 144/170 \approx 84.7\%\) полной энергии; ранга 2 — \(169/170 \approx 99.4\%\). Второе слагаемое уменьшает ошибку с \(\sqrt{26}\approx 5.10\) до \(1\).

Ответ: \(A_1 = 12\,\mathbf{u}_1\mathbf{v}_1^T\), \(A_2 = 12\,\mathbf{u}_1\mathbf{v}_1^T + 5\,\mathbf{u}_2\mathbf{v}_2^T\); \(\|A-A_1\|_F = \sqrt{26} \approx 5.10\); \(\|A-A_2\|_F = 1\).

4.7 Энергия и сравнение объёма памяти (Лаба 8, Задание 7)

У матрицы \(M \in \mathbb{R}^{1000 \times 800}\) сингулярные числа \(\sigma_1 = 120\), \(\sigma_2 = 40\), \(\sigma_3 = 10\), \(\sigma_4 = 2\), остальные нулевые. Найдите наименьшее \(k\), при котором ранг-\(k\) приближение сохраняет не менее \(99\%\) полной энергии. Сравните объём хранения этого приближения с полной матрицей.

Нажмите, чтобы увидеть решение

Ключевая идея: доля энергии первых \(k\) сингулярных чисел — \(\sum_{i=1}^k \sigma_i^2 / \sum_{i=1}^r \sigma_i^2\). Ищем минимальное \(k\) с долей \(\geq 99\%\), затем сравниваем затраты памяти.

Шаг 1 — полная энергия.

\[E_{\text{total}} = \sigma_1^2 + \sigma_2^2 + \sigma_3^2 + \sigma_4^2 = 120^2 + 40^2 + 10^2 + 2^2 = 14400 + 1600 + 100 + 4 = 16104\]

Шаг 2 — проверка \(k = 1\).

\[E_1 = 14400, \qquad \frac{E_1}{E_{\text{total}}} = \frac{14400}{16104} \approx 89.4\% < 99\%\]

Шаг 3 — проверка \(k = 2\).

\[E_2 = 14400 + 1600 = 16000, \qquad \frac{E_2}{E_{\text{total}}} = \frac{16000}{16104} \approx 99.35\% \geq 99\%\ ✓\]

Наименьшее \(k\) с долей не менее \(99\%\): \(\boxed{k = 2}\).

Шаг 4 — память.

• Полная матрица: \(1000 \times 800 = 800{,}000\) чисел.
• Ранг-2 SVD: \(k\) левых сингулярных векторов (\(mk = 2000\)), \(k\) правых (\(nk = 1600\)), \(k\) сингулярных чисел (\(2\)). Итого \(k(m+n+1) = 2(1000+800+1) = 3602\) числа.
• Коэффициент сжатия: \(3602 / 800{,}000 \approx 0.45\%\).

Ранг-2 SVD занимает меньше \(0.5\%\) памяти от полной матрицы при сохранении свыше \(99\%\) энергии.

Шаг 5 — где ещё используют.

Кроме сжатия изображений: рекомендательные системы (матричная факторизация, collaborative filtering), обработка естественного языка (latent semantic analysis), анализ сетей (сжатие матриц смежности), конвейеры машинного обучения, где у матрицы данных малый эффективный ранг.

Ответ: \(k = 2\) (доля энергии \(\approx 99.35\%\)). Память: \(3{,}602\) числа против \(800{,}000\) у полной матрицы; коэффициент сжатия \(\approx 0.45\%\).

4.8 Полное SVD и лучшее приближение ранга 1 (Лаба 8, Задание 8)

Пусть \(A = \begin{bmatrix} 1 & 1 & 0 \\ 0 & 1 & 1 \end{bmatrix}\). Найдите полное SVD, опишите четыре фундаментальных подпространства и запишите лучшее приближение ранга 1 — \(A_1\).

Нажмите, чтобы увидеть решение

Ключевая идея: для матрицы \(2 \times 3\) ранга \(2\) матрица \(A^TA\) размера \(3 \times 3\) имеет одно нулевое собственное значение. Находим все три собственных вектора \(A^TA\), строим \(U\) по двум ненулевым сингулярным парам, затем \(A_1\) — доминирующее слагаемое.

Шаг 1 — \(A^TA\) (\(3\times 3\)).

\[A^TA = \begin{bmatrix}1&0\\1&1\\0&1\end{bmatrix}\begin{bmatrix}1&1&0\\0&1&1\end{bmatrix} = \begin{bmatrix}1&1&0\\1&2&1\\0&1&1\end{bmatrix}\]

Шаг 2 — собственные значения \(A^TA\).

\[\det(A^TA - \lambda I) = (1-\lambda)\bigl[(2-\lambda)(1-\lambda)-1\bigr] - \bigl[(1-\lambda)\bigr]\] \[= (1-\lambda)\bigl[\lambda^2-3\lambda+1\bigr] - (1-\lambda) = (1-\lambda)\bigl[\lambda^2-3\lambda\bigr] = (1-\lambda)\cdot\lambda(\lambda-3)\]

Собственные значения: \(\lambda_1 = 3\), \(\lambda_2 = 1\), \(\lambda_3 = 0\). Значит \(\sigma_1 = \sqrt{3}\), \(\sigma_2 = 1\), \(\sigma_3 = 0\), \(\text{rank}(A) = 2\).

Шаг 3 — правые сингулярные векторы (столбцы \(V\)).

Для \(\lambda_1 = 3\): из \((A^TA - 3I)\mathbf{v} = 0\) получаем \(-2v_1+v_2=0\), \(v_1-v_2+v_3=0\), \(v_2-2v_3=0\), откуда \(v_2 = 2v_3\), \(v_1 = v_3\), то есть \(\mathbf{v}_1 \propto (1,2,1)^T\). \[\mathbf{v}_1 = \frac{1}{\sqrt{6}}\begin{bmatrix}1\\2\\1\end{bmatrix}\]

Для \(\lambda_2 = 1\): \((A^TA - I)\mathbf{v} = 0\): \(v_2 = 0\), \(v_1 + v_3 = 0\), значит \(\mathbf{v}_2 \propto (1,0,-1)^T\). \[\mathbf{v}_2 = \frac{1}{\sqrt{2}}\begin{bmatrix}1\\0\\-1\end{bmatrix}\]

Для \(\lambda_3 = 0\): ядро \(A\): \(v_1+v_2=0\), \(v_2+v_3=0\), поэтому \(\mathbf{v}_3 \propto (1,-1,1)^T\). \[\mathbf{v}_3 = \frac{1}{\sqrt{3}}\begin{bmatrix}1\\-1\\1\end{bmatrix}\]

Шаг 4 — левые сингулярные векторы.

\[\mathbf{u}_1 = \frac{A\mathbf{v}_1}{\sigma_1} = \frac{1}{\sqrt{3}}\cdot\frac{1}{\sqrt{6}}\begin{bmatrix}1&1&0\\0&1&1\end{bmatrix}\begin{bmatrix}1\\2\\1\end{bmatrix} = \frac{1}{\sqrt{18}}\begin{bmatrix}3\\3\end{bmatrix} = \frac{1}{\sqrt{2}}\begin{bmatrix}1\\1\end{bmatrix}\]

\[\mathbf{u}_2 = \frac{A\mathbf{v}_2}{\sigma_2} = \frac{1}{\sqrt{2}}\begin{bmatrix}1&1&0\\0&1&1\end{bmatrix}\begin{bmatrix}1\\0\\-1\end{bmatrix} = \frac{1}{\sqrt{2}}\begin{bmatrix}1\\-1\end{bmatrix}\]

Шаг 5 — собрать SVD.

\[U = \frac{1}{\sqrt{2}}\begin{bmatrix}1&1\\1&-1\end{bmatrix}, \quad \Sigma = \begin{bmatrix}\sqrt{3}&0&0\\0&1&0\end{bmatrix}, \quad V = \begin{bmatrix}1/\sqrt{6}&1/\sqrt{2}&1/\sqrt{3}\\2/\sqrt{6}&0&-1/\sqrt{3}\\1/\sqrt{6}&-1/\sqrt{2}&1/\sqrt{3}\end{bmatrix}\]

Шаг 6 — четыре подпространства.

• \(C(A) = \text{span}\{\mathbf{u}_1, \mathbf{u}_2\} = \mathbb{R}^2\) (всё пространство, размерность 2)
• \(N(A^T) = \{0\}\) (размерность 0, так как \(m = r = 2\))
• \(C(A^T) = \text{span}\{\mathbf{v}_1, \mathbf{v}_2\}\) (размерность 2)
• \(N(A) = \text{span}\{\mathbf{v}_3\} = \text{span}\left\{\tfrac{1}{\sqrt{3}}(1,-1,1)^T\right\}\) (размерность 1)

Шаг 7 — лучшее приближение ранга 1.

\[A_1 = \sigma_1\,\mathbf{u}_1\mathbf{v}_1^T = \sqrt{3}\cdot\frac{1}{\sqrt{2}}\begin{bmatrix}1\\1\end{bmatrix}\cdot\frac{1}{\sqrt{6}}\begin{bmatrix}1&2&1\end{bmatrix} = \frac{\sqrt{3}}{\sqrt{12}}\begin{bmatrix}1&2&1\\1&2&1\end{bmatrix} = \frac{1}{2}\begin{bmatrix}1&2&1\\1&2&1\end{bmatrix}\]

Ответ: \(\sigma_1 = \sqrt{3}\), \(\sigma_2 = 1\), \(\sigma_3 = 0\), \(\text{rank}(A) = 2\). Лучшее приближение ранга 1: \(A_1 = \tfrac{1}{2}\begin{bmatrix}1&2&1\\1&2&1\end{bmatrix}\).

4.9 Сингулярные числа и ранг трёх матриц (Домашнее задание 8, Задание 1)

Найдите сингулярные числа и ранг каждой матрицы: (a) \(A = \begin{bmatrix} 3 & 0 \\ 0 & -5 \end{bmatrix}\), (b) \(B = \begin{bmatrix} 1 & 2 \\ 2 & 4 \end{bmatrix}\), (c) \(C = \begin{bmatrix} 0 & 0 \\ 0 & 0 \end{bmatrix}\).

Нажмите, чтобы увидеть решение

Ключевая идея: сингулярные числа — корни из собственных значений \(A^TA\). Для диагональных или вырожденных по рангу матриц выкладки упрощаются: у диагональной \(A\) с вещественными элементами на диагонали стоят \(|\text{диагональ}|\) в подходящем порядке; при дефиците ранга есть нулевые сингулярные числа.

Часть (а) — \(A = \begin{bmatrix}3&0\\0&-5\end{bmatrix}\).

Шаг 1: \(A^TA = \begin{bmatrix}9&0\\0&25\end{bmatrix}\), собственные значения \(\lambda_1=25\), \(\lambda_2=9\).

Шаг 2: \(\sigma_1 = 5\), \(\sigma_2 = 3\). Сингулярные числа неотрицательны, хотя \(A_{22} = -5\).

Шаг 3: оба сингулярных числа положительны, \(\text{rank}(A) = 2\).

Часть (б) — \(B = \begin{bmatrix}1&2\\2&4\end{bmatrix}\).

Шаг 1: вторая строка — удвоенная первая, \(\text{rank}(B) = 1\).

Шаг 2: \(B^TB = \begin{bmatrix}5&10\\10&20\end{bmatrix}\).

Шаг 3: \(\det(B^TB - \lambda I) = \lambda^2 - 25\lambda = \lambda(\lambda-25) = 0\), значит \(\lambda_1 = 25\), \(\lambda_2 = 0\).

Шаг 4: \(\sigma_1 = 5\), \(\sigma_2 = 0\), \(\text{rank}(B) = 1\).

Часть (в) — \(C = \begin{bmatrix}0&0\\0&0\end{bmatrix}\).

Шаг 1: \(C^TC = 0\), все собственные значения \(0\).

Шаг 2: \(\sigma_1 = \sigma_2 = 0\), \(\text{rank}(C) = 0\).

Ответ: (а) \(\sigma_1=5\), \(\sigma_2=3\), \(\text{rank}=2\). (б) \(\sigma_1=5\), \(\sigma_2=0\), \(\text{rank}=1\). (в) \(\sigma_1=\sigma_2=0\), \(\text{rank}=0\).

4.10 Полное SVD матрицы \(3 \times 2\) (Домашнее задание 8, Задание 2)

Найдите полное SVD матрицы \(A = \begin{bmatrix} 1 & 0 \\ 0 & 2 \\ 0 & 0 \end{bmatrix}\).

Нажмите, чтобы увидеть решение

Ключевая идея: «высокая» матрица \(3\times 2\); \(A^TA\) диагональна — вычисления короткие. Матрицу \(U\) нужно дополнить до ортогональной \(3\times 3\), добавив столбец из ядра \(A^T\).

Шаг 1 — \(A^TA\) (\(2\times 2\)).

\[A^TA = \begin{bmatrix}1&0&0\\0&2&0\end{bmatrix}\begin{bmatrix}1&0\\0&2\\0&0\end{bmatrix} = \begin{bmatrix}1&0\\0&4\end{bmatrix}\]

Шаг 2 — спектр и сингулярные числа.

\(A^TA = \text{diag}(1,4)\), значит \(\lambda_1 = 4\), \(\lambda_2 = 1\), \(\sigma_1 = 2\), \(\sigma_2 = 1\), \(\text{rank}(A)=2\).

Шаг 3 — правые сингулярные векторы (столбцы \(V\)).

Для \(\lambda_1 = 4\): \(\mathbf{v}_1 = (0,1)^T\). Для \(\lambda_2 = 1\): \(\mathbf{v}_2 = (1,0)^T\). \[V = \begin{bmatrix}0&1\\1&0\end{bmatrix}\]

Шаг 4 — левые сингулярные векторы.

\[\mathbf{u}_1 = \frac{A\mathbf{v}_1}{\sigma_1} = \frac{1}{2}\begin{bmatrix}0\\2\\0\end{bmatrix} = \begin{bmatrix}0\\1\\0\end{bmatrix}\]

\[\mathbf{u}_2 = \frac{A\mathbf{v}_2}{\sigma_2} = \frac{1}{1}\begin{bmatrix}1\\0\\0\end{bmatrix} = \begin{bmatrix}1\\0\\0\end{bmatrix}\]

Шаг 5 — дополнить \(U\) до \(3\times 3\).

Нужен \(\mathbf{u}_3\), ортогональный \(\mathbf{u}_1 = (0,1,0)^T\) и \(\mathbf{u}_2 = (1,0,0)^T\); единственный единичный вектор: \[\mathbf{u}_3 = \begin{bmatrix}0\\0\\1\end{bmatrix}\]

\[U = \begin{bmatrix}0&1&0\\1&0&0\\0&0&1\end{bmatrix}\]

Шаг 6 — проверка.

\[A = U\Sigma V^T = \begin{bmatrix}0&1&0\\1&0&0\\0&0&1\end{bmatrix}\begin{bmatrix}2&0\\0&1\\0&0\end{bmatrix}\begin{bmatrix}0&1\\1&0\end{bmatrix}\]

Проверка: \(U\Sigma V^T = A\). ✓

Ответ: \(U = \begin{bmatrix}0&1&0\\1&0&0\\0&0&1\end{bmatrix}\), \(\Sigma = \begin{bmatrix}2&0\\0&1\\0&0\end{bmatrix}\), \(V = \begin{bmatrix}0&1\\1&0\end{bmatrix}\); \(\sigma_1 = 2\), \(\sigma_2 = 1\), \(\text{rank}(A)=2\).

4.11 Усечённое (thin) SVD «высокой» матрицы (Домашнее задание 8, Задание 3)

Найдите reduced (thin) SVD матрицы \(A = \begin{bmatrix} 3 & 0 \\ 0 & 0 \\ 0 & 4 \end{bmatrix}\).

Нажмите, чтобы увидеть решение

Ключевая идея: в усечённом SVD оставляют только \(r\) ненулевых сингулярных троек: \(A = \hat{U}\hat{\Sigma}\hat{V}^T\), где \(\hat{U}\) размера \(m\times r\), \(\hat{\Sigma}\) — \(r\times r\) диагональная, \(\hat{V}\) — \(n\times r\). Здесь \(r=2\), третий столбец \(U\) из полного SVD не нужен.

Шаг 1 — \(A^TA\) (\(2\times 2\)).

\[A^TA = \begin{bmatrix}3&0&0\\0&0&4\end{bmatrix}\begin{bmatrix}3&0\\0&0\\0&4\end{bmatrix} = \begin{bmatrix}9&0\\0&16\end{bmatrix}\]

Шаг 2 — собственные значения и сингулярные числа.

\(A^TA = \text{diag}(9,16)\), значит \(\lambda_1 = 16\), \(\lambda_2 = 9\), \(\sigma_1 = 4\), \(\sigma_2 = 3\), \(\text{rank}(A)=2\).

Шаг 3 — столбцы \(\hat{V}\).

Для \(\lambda_1 = 16\): \(\mathbf{v}_1 = (0,1)^T\). Для \(\lambda_2 = 9\): \(\mathbf{v}_2 = (1,0)^T\). \[\hat{V} = \begin{bmatrix}0&1\\1&0\end{bmatrix}\]

Шаг 4 — столбцы \(\hat{U}\).

\[\mathbf{u}_1 = \frac{A\mathbf{v}_1}{\sigma_1} = \frac{1}{4}\begin{bmatrix}3&0\\0&0\\0&4\end{bmatrix}\begin{bmatrix}0\\1\end{bmatrix} = \begin{bmatrix}0\\0\\1\end{bmatrix}\]

\[\mathbf{u}_2 = \frac{A\mathbf{v}_2}{\sigma_2} = \frac{1}{3}\begin{bmatrix}3\\0\\0\end{bmatrix} = \begin{bmatrix}1\\0\\0\end{bmatrix}\]

\[\hat{U} = \begin{bmatrix}0&1\\0&0\\1&0\end{bmatrix}\]

Шаг 5 — собрать thin SVD.

\[A = \hat{U}\hat{\Sigma}\hat{V}^T = \begin{bmatrix}0&1\\0&0\\1&0\end{bmatrix}\begin{bmatrix}4&0\\0&3\end{bmatrix}\begin{bmatrix}0&1\\1&0\end{bmatrix}\]

Проверка: произведение равно \(A\). ✓

Ответ: \(\hat{U} = \begin{bmatrix}0&1\\0&0\\1&0\end{bmatrix}\), \(\hat{\Sigma} = \begin{bmatrix}4&0\\0&3\end{bmatrix}\), \(\hat{V} = \begin{bmatrix}0&1\\1&0\end{bmatrix}\); \(\sigma_1 = 4\), \(\sigma_2 = 3\).

4.12 SVD вырожденной матрицы \(2 \times 2\) (Домашнее задание 8, Задание 4)

Найдите сингулярные числа, ранг и полное SVD для \(A = \begin{bmatrix} 1 & 1 \\ 1 & 1 \end{bmatrix}\).

Нажмите, чтобы увидеть решение

Ключевая идея: строки совпадают, ранг \(1\), одно ненулевое сингулярное число; \(U\) дополняют до ортогональной \(2\times 2\) вектором, ортогональным \(\mathbf{u}_1\).

Шаг 1 — \(A^TA\).

\[A^TA = \begin{bmatrix}1&1\\1&1\end{bmatrix}\begin{bmatrix}1&1\\1&1\end{bmatrix} = \begin{bmatrix}2&2\\2&2\end{bmatrix}\]

Шаг 2 — собственные значения и сингулярные числа.

\(\det(A^TA - \lambda I) = \lambda^2-4\lambda = \lambda(\lambda-4) = 0\). Значит \(\lambda_1 = 4\), \(\lambda_2 = 0\), \(\sigma_1 = 2\), \(\sigma_2 = 0\), \(\text{rank}(A)=1\).

Шаг 3 — правые сингулярные векторы.

Для \(\lambda_1 = 4\): \((A^TA - 4I)\mathbf{v} = 0 \Rightarrow v_1=v_2\), \(\mathbf{v}_1 = \tfrac{1}{\sqrt{2}}(1,1)^T\).

Для \(\lambda_2 = 0\): ортодополнение, \(\mathbf{v}_2 = \tfrac{1}{\sqrt{2}}(1,-1)^T\).

\[V = \frac{1}{\sqrt{2}}\begin{bmatrix}1&1\\1&-1\end{bmatrix}\]

Шаг 4 — левые сингулярные векторы.

\[\mathbf{u}_1 = \frac{A\mathbf{v}_1}{\sigma_1} = \frac{1}{\sqrt{2}}\begin{bmatrix}1\\1\end{bmatrix}\]

Для \(\mathbf{u}_2\): ортогонально \(\mathbf{u}_1\), \(\mathbf{u}_2 = \tfrac{1}{\sqrt{2}}(1,-1)^T\).

\[U = \frac{1}{\sqrt{2}}\begin{bmatrix}1&1\\1&-1\end{bmatrix}\]

Шаг 5 — проверка.

\[A = U\Sigma V^T = \frac{1}{\sqrt{2}}\begin{bmatrix}1&1\\1&-1\end{bmatrix}\begin{bmatrix}2&0\\0&0\end{bmatrix}\frac{1}{\sqrt{2}}\begin{bmatrix}1&1\\1&-1\end{bmatrix}\]

Умножение даёт \(A\). ✓

Ответ: \(\sigma_1 = 2\), \(\sigma_2 = 0\), \(\text{rank}(A)=1\). \(U = V = \tfrac{1}{\sqrt{2}}\begin{bmatrix}1&1\\1&-1\end{bmatrix}\), \(\Sigma = \begin{bmatrix}2&0\\0&0\end{bmatrix}\).

4.13 SVD «широкой» матрицы (Домашнее задание 8, Задание 5)

Найдите сингулярные числа, ранг и полное SVD для \(A = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 2 & 0 \end{bmatrix}\).

Нажмите, чтобы увидеть решение

Ключевая идея: матрица \(2\times 3\); \(A^TA\) диагональна \(3\times 3\). Матрицу \(V\) дополняют до ортогональной \(3\times 3\), включая базисный вектор из ядра \(A\).

Шаг 1 — \(A^TA\) (\(3\times 3\)).

\[A^TA = \begin{bmatrix}1&0&0\\0&4&0\\0&0&0\end{bmatrix}\]

Шаг 2 — собственные значения и сингулярные числа.

\(\lambda_1 = 4\), \(\lambda_2 = 1\), \(\lambda_3 = 0\); \(\sigma_1 = 2\), \(\sigma_2 = 1\), \(\sigma_3 = 0\), \(\text{rank}(A)=2\).

Шаг 3 — столбцы \(V\).

\(\mathbf{v}_1 = (0,1,0)^T\), \(\mathbf{v}_2 = (1,0,0)^T\), \(\mathbf{v}_3 = (0,0,1)^T\).

\[V = \begin{bmatrix}0&1&0\\1&0&0\\0&0&1\end{bmatrix}\]

Шаг 4 — левые сингулярные векторы.

\[\mathbf{u}_1 = \begin{bmatrix}0\\1\end{bmatrix}, \qquad \mathbf{u}_2 = \begin{bmatrix}1\\0\end{bmatrix}, \qquad U = \begin{bmatrix}0&1\\1&0\end{bmatrix}\]

Шаг 5 — SVD и проверка.

\[A = U\Sigma V^T = \begin{bmatrix}0&1\\1&0\end{bmatrix}\begin{bmatrix}2&0&0\\0&1&0\end{bmatrix}\begin{bmatrix}0&1&0\\1&0&0\\0&0&1\end{bmatrix} = A.\ \checkmark\]

Ответ: \(\sigma_1 = 2\), \(\sigma_2 = 1\), \(\sigma_3 = 0\), \(\text{rank}(A)=2\). \(U\), \(\Sigma\), \(V\) как выше.

4.14 Верно/неверно: свойства SVD (Домашнее задание 8, Задание 6)

Для каждого утверждения укажите, верно оно или нет, с кратким обоснованием.

1. У любой квадратной матрицы единственное SVD.

2. Сингулярные числа \(A\) всегда неотрицательны.

3. Если \(A\) симметрична и положительно определена (SPD), то её сингулярные числа совпадают с собственными значениями.

4. Ранг матрицы равен числу ненулевых сингулярных чисел.

Нажмите, чтобы увидеть решение

Ключевая идея: проверяются базовые факты о сингулярных числах и SVD. Сингулярные числа однозначны; векторы (и пара \(U\), \(V\)) — в общем случае нет.

Часть (а) — «у любой квадратной матрицы единственное SVD». — НЕВЕРНО.

Шаг 1: SVD существует у любой (в том числе квадратной) матрицы.

Шаг 2: Единственность полного разложения не гарантируется: \(\sigma_i\) определяются однозначно, а сингулярные векторы — нет. При кратных \(\sigma_i\) можно поворачивать базис в соответствующем собственном подпространстве \(A^TA\); при различных \(\sigma_i\) смена знака \(\mathbf{v}_i\) с согласованной правкой \(\mathbf{u}_i\) даёт другое допустимое SVD.

Итог: существование есть, каноническая единственность пары \((U,V)\) — нет.

Часть (б) — «сингулярные числа всегда \(\geq 0\)». — ВЕРНО.

Шаг 1: \(\sigma_i = \sqrt{\lambda_i(A^TA)}\).

Шаг 2: \(A^TA\) симметрична и PSD: \(\mathbf{x}^T(A^TA)\mathbf{x} = \|A\mathbf{x}\|^2 \geq 0\), значит \(\lambda_i(A^TA) \geq 0\).

Шаг 3: корень из неотрицательного числа неотрицателен.

Часть (в) — для SPD сингулярные числа равны собственным. — ВЕРНО.

Шаг 1: \(A = Q\Lambda Q^T\), все \(\lambda_i > 0\).

Шаг 2: \(A^TA = A^2 = Q\Lambda^2 Q^T\), собственные значения \(A^TA\) — \(\lambda_i^2\).

Шаг 3: \(\sigma_i = \sqrt{\lambda_i^2} = |\lambda_i| = \lambda_i\).

Часть (г) — ранг равен числу ненулевых сингулярных чисел. — ВЕРНО.

Шаг 1: \(\dim C(A)\) по SVD равно числу положительных \(\sigma_i\).

Шаг 2: в сумме \(A = \sum \sigma_i \mathbf{u}_i\mathbf{v}_i^T\) нулевые \(\sigma_i\) не дают вклада.

Ответ: (а) неверно — единственны сингулярные числа, не всё разложение. (б) верно. (в) верно для SPD. (г) верно (число строго положительных \(\sigma_i\)).

4.15 SVD симметричной матрицы (Домашнее задание 8, Задание 7)

Найдите SVD матрицы \(A = \begin{bmatrix} 3 & 1 \\ 1 & 3 \end{bmatrix}\).

Нажмите, чтобы увидеть решение

Ключевая идея: \(A\) симметрична, поэтому спектральное разложение сразу даёт SVD: \(U = V = Q\), сингулярные числа совпадают с положительными собственными значениями.

Шаг 1 — про \(A^TA\).

Так как \(A = A^T\), можно было бы смотреть \(A^TA = A^2\), но проще сразу диагонализовать \(A\).

Шаг 2 — собственные значения \(A\).

\[\det(A - \lambda I) = (3-\lambda)^2 - 1 = \lambda^2 - 6\lambda + 8 = (\lambda-4)(\lambda-2) = 0\]

Значит \(\lambda_1 = 4\), \(\lambda_2 = 2\); оба положительны — \(A\) есть SPD.

Шаг 3 — сингулярные числа.

\[\sigma_1 = \lambda_1 = 4, \qquad \sigma_2 = \lambda_2 = 2\]

Шаг 4 — собственные векторы \(A\) (= правые и левые сингулярные).

Для \(\lambda_1 = 4\): \((A-4I)\mathbf{v} = 0 \Rightarrow v_1=v_2\), \(\mathbf{v}_1 = \tfrac{1}{\sqrt{2}}(1,1)^T\).

Для \(\lambda_2 = 2\): \((A-2I)\mathbf{v} = 0 \Rightarrow v_2=-v_1\), \(\mathbf{v}_2 = \tfrac{1}{\sqrt{2}}(1,-1)^T\).

\[Q = V = U = \frac{1}{\sqrt{2}}\begin{bmatrix}1&1\\1&-1\end{bmatrix}\]

Шаг 5 — проверка \(\mathbf{u}_i = A\mathbf{v}_i/\sigma_i\).

\[\mathbf{u}_1 = \frac{A\mathbf{v}_1}{\sigma_1} = \mathbf{v}_1 \checkmark, \qquad \mathbf{u}_2 = \frac{A\mathbf{v}_2}{\sigma_2} = \mathbf{v}_2 \checkmark\]

Шаг 6 — SVD.

\[A = Q\begin{bmatrix}4&0\\0&2\end{bmatrix}Q^T = \frac{1}{\sqrt{2}}\begin{bmatrix}1&1\\1&-1\end{bmatrix}\begin{bmatrix}4&0\\0&2\end{bmatrix}\frac{1}{\sqrt{2}}\begin{bmatrix}1&1\\1&-1\end{bmatrix}\]

Умножение даёт \(A\). ✓

Ответ: \(\sigma_1 = 4\), \(\sigma_2 = 2\). \(U = V = \tfrac{1}{\sqrt{2}}\begin{bmatrix}1&1\\1&-1\end{bmatrix}\), \(\Sigma = \begin{bmatrix}4&0\\0&2\end{bmatrix}\).

4.16 Ранг и SVD по известным сингулярным числам (Домашнее задание 8, Задание 8)

У матрицы \(A\) сингулярные числа \(\sigma_1 = 5\), \(\sigma_2 = 3\), \(\sigma_3 = 0\). (а) Каков ранг \(A\)? (б) Запишите SVD для \(A^T\) через сингулярные векторы \(A\). (в) Каковы сингулярные числа \(2A\)?

Нажмите, чтобы увидеть решение

Ключевая идея: из \(A = U\Sigma V^T\) свойства \(A^T\) и \(cA\) читаются алгебраическими формулами SVD, даже без явного размера матрицы.

Часть (а) — ранг.

Шаг 1: ранг равен числу строго положительных сингулярных чисел.

Шаг 2: \(\sigma_1 = 5 > 0\), \(\sigma_2 = 3 > 0\), \(\sigma_3 = 0\) — два положительных.

\[\text{rank}(A) = 2\]

Часть (б) — \(A^T\).

Шаг 1: \(A^T = (U\Sigma V^T)^T = V\Sigma^T U^T\).

Шаг 2: для диагональной \(\Sigma = \text{diag}(5,3,0)\) имеем \(\Sigma^T = \Sigma\).

Шаг 3: \(A^T = V\Sigma U^T\); левые сингулярные векторы \(A^T\) — столбцы \(V\), правые — столбцы \(U\).

Шаг 4: сингулярные числа те же: \(5, 3, 0\).

Часть (в) — \(2A\).

Шаг 1: \(2A = U(2\Sigma)V^T\).

Шаг 2: \(U\), \(V\) не меняются; сингулярные числа умножаются на \(|2| = 2\):

\[\sigma_1(2A) = 10, \qquad \sigma_2(2A) = 6, \qquad \sigma_3(2A) = 0\]

Ответ: (а) \(\text{rank}(A)=2\). (б) \(A^T = V\Sigma U^T\), те же \(\sigma\). (в) у \(2A\): \(10, 6, 0\).

4.17 \(A^TA\) и SVD для нильпотентной матрицы (Домашнее задание 8, Задание 9)

Пусть \(A = \begin{bmatrix} 0 & 1 \\ 0 & 0 \end{bmatrix}\). Найдите \(A^TA\), сингулярные числа и полное SVD.

Нажмите, чтобы увидеть решение

Ключевая идея: \(A\) нильпотентна (\(A^2 = 0\)), спектр по собственным векторам «плохой», но SVD у любой матрицы есть. Здесь \(A^TA\) диагональна — счёт короткий.

Шаг 1 — \(A^TA\).

\[A^TA = \begin{bmatrix}0&0\\1&0\end{bmatrix}\begin{bmatrix}0&1\\0&0\end{bmatrix} = \begin{bmatrix}0&0\\0&1\end{bmatrix}\]

Шаг 2 — собственные значения и сингулярные числа.

\(A^TA = \text{diag}(0,1)\), значит \(\lambda_1 = 1\), \(\lambda_2 = 0\), \[\sigma_1 = 1, \qquad \sigma_2 = 0, \qquad \text{rank}(A) = 1\]

Замечание: у \(A\) собственные значения \(0,0\), а \(\sigma_1 = 1\); сингулярные числа и спектр — разные вещи.

Шаг 3 — столбцы \(V\).

Для \(\lambda_1 = 1\): из \(A^TA\mathbf{v} = \mathbf{v}\) следует \(v_1 = 0\), \(\mathbf{v}_1 = (0,1)^T\).

Для \(\lambda_2 = 0\): \(v_2 = 0\), \(\mathbf{v}_2 = (1,0)^T\).

\[V = \begin{bmatrix}0&1\\1&0\end{bmatrix}\]

Шаг 4 — левые сингулярные векторы.

\[\mathbf{u}_1 = \frac{A\mathbf{v}_1}{\sigma_1} = \begin{bmatrix}1\\0\end{bmatrix}\]

\(\mathbf{u}_2\) ортогонален \(\mathbf{u}_1\): \(\mathbf{u}_2 = (0,1)^T\), \(U = I_2\).

Шаг 5 — проверка.

\[A = U\Sigma V^T = I_2 \begin{bmatrix}1&0\\0&0\end{bmatrix}\begin{bmatrix}0&1\\1&0\end{bmatrix} = A.\ \checkmark\]

Ответ: \(A^TA = \begin{bmatrix}0&0\\0&1\end{bmatrix}\); \(\sigma_1 = 1\), \(\sigma_2 = 0\), \(\text{rank}(A)=1\); \(U = I_2\), \(\Sigma = \begin{bmatrix}1&0\\0&0\end{bmatrix}\), \(V = \begin{bmatrix}0&1\\1&0\end{bmatrix}\).

4.18 SVD диагональной матрицы (Туториал 8, Пример 1)

Найдите полное SVD матрицы \(A = \begin{bmatrix} 1 & 0 \\ 0 & 2 \end{bmatrix}\).

Нажмите, чтобы увидеть решение

Ключевая идея: для диагональной \(A\) матрица \(A^TA\) тоже диагональна; стандартный алгоритм: \(V\) из \(A^TA\), затем \(\Sigma\), затем \(U\).

Шаг 1 — \(A^TA\).

\[A^TA = \begin{bmatrix} 1 & 0 \\ 0 & 2 \end{bmatrix}^T \begin{bmatrix} 1 & 0 \\ 0 & 2 \end{bmatrix} = \begin{bmatrix} 1 & 0 \\ 0 & 4 \end{bmatrix}\]

Шаг 2 — собственные значения \(A^TA\).

\(\lambda_1 = 4\), \(\lambda_2 = 1\) (в невозрастающем порядке: \(\lambda_1 \geq \lambda_2\)).

Шаг 3 — сингулярные числа.

\[\sigma_1 = 2, \qquad \sigma_2 = 1, \qquad \Sigma = \begin{bmatrix} 2 & 0 \\ 0 & 1 \end{bmatrix}\]

Шаг 4 — столбцы \(V\).

Для \(\lambda_1 = 4\): \(\mathbf{e}_2 = (0,1)^T\). Для \(\lambda_2 = 1\): \(\mathbf{e}_1 = (1,0)^T\).

\[\mathbf{v}_1 = \begin{bmatrix} 0 \\ 1 \end{bmatrix}, \qquad \mathbf{v}_2 = \begin{bmatrix} 1 \\ 0 \end{bmatrix}, \qquad V = \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix}\]

Шаг 5 — левые сингулярные векторы.

\[\mathbf{u}_1 = \frac{A\mathbf{v}_1}{\sigma_1} = \begin{bmatrix} 0 \\ 1 \end{bmatrix}, \qquad \mathbf{u}_2 = \frac{A\mathbf{v}_2}{\sigma_2} = \begin{bmatrix} 1 \\ 0 \end{bmatrix}, \qquad U = \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix}\]

Шаг 6 — проверка.

\[A = U\Sigma V^T = \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix}\begin{bmatrix} 2 & 0 \\ 0 & 1 \end{bmatrix}\begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix} = A.\ \checkmark\]

Ответ: \(A = U\Sigma V^T\) как выше; \(\sigma_1 = 2\), \(\sigma_2 = 1\).

4.19 Ранг и размерности подпространств по сингулярным числам (Туториал 8, Пример 2)

Матрица \(A \in \mathbb{R}^{5 \times 4}\) имеет сингулярные числа \(10, 5, 2\) и ещё одно нулевое. Найдите ранг и размерности всех четырёх фундаментальных подпространств.

Нажмите, чтобы увидеть решение

Ключевая идея: ранг — число ненулевых сингулярных чисел; размерности — из теоремы о ранге и дефекте.

Шаг 1 — ранг.

Три ненулевых сингулярных числа (\(10, 5, 2\)), значит \[r = \text{rank}(A) = 3\]

Шаг 2 — размерности.

\(m = 5\), \(n = 4\).

• \(C(A) \subseteq \mathbb{R}^5\): \(\dim C(A) = 3\).
• \(N(A^T) \subseteq \mathbb{R}^5\): \(\dim N(A^T) = m - r = 2\).
• \(C(A^T) \subseteq \mathbb{R}^4\): \(\dim C(A^T) = 3\).
• \(N(A) \subseteq \mathbb{R}^4\): \(\dim N(A) = n - r = 1\).

Смысл: в SVD явно заданы ортонормированные базисы: \(\mathbf{u}_1,\mathbf{u}_2,\mathbf{u}_3\) в \(C(A)\); \(\mathbf{u}_4,\mathbf{u}_5\) в \(N(A^T)\); \(\mathbf{v}_1,\mathbf{v}_2,\mathbf{v}_3\) в \(C(A^T)\); \(\mathbf{v}_4\) в \(N(A)\).

Ответ: \(\text{rank}(A)=3\); \(\dim C(A)=3\), \(\dim N(A^T)=2\), \(\dim C(A^T)=3\), \(\dim N(A)=1\).

4.20 SVD матрицы ранга 1 (Туториал 8, Пример 3)

Найдите SVD матрицы \(A = \begin{bmatrix} 1 & 2 \\ 2 & 4 \\ 3 & 6 \end{bmatrix}\).

Нажмите, чтобы увидеть решение

Ключевая идея: каждая строка — кратная \((1,2)\), ранг \(1\), одно ненулевое сингулярное число; затем достраивают ортонормированные \(U\) и \(V\).

Шаг 1 — \(A^TA\).

\[A^TA = \begin{bmatrix} 14 & 28 \\ 28 & 56 \end{bmatrix}\]

Шаг 2 — собственные значения \(A^TA\).

\[\det(A^TA - \lambda I) = \lambda^2 - 70\lambda = \lambda(\lambda - 70)\]

\(\lambda_1 = 70\), \(\lambda_2 = 0\).

Шаг 3 — сингулярные числа.

\[\sigma_1 = \sqrt{70}, \qquad \sigma_2 = 0\]

Шаг 4 — правые сингулярные векторы.

Из \((A^TA - 70I)\mathbf{v} = 0\) получаем \(\mathbf{v}_1 = \frac{1}{\sqrt{5}}\begin{bmatrix} 1 \\ 2 \end{bmatrix}\); ортогонально ему \(\mathbf{v}_2 = \frac{1}{\sqrt{5}}\begin{bmatrix} -2 \\ 1 \end{bmatrix}\).

(Проверка: \(\mathbf{v}_1 \cdot \mathbf{v}_2 = 0\). ✓)

\[V = \frac{1}{\sqrt{5}}\begin{bmatrix} 1 & -2 \\ 2 & 1 \end{bmatrix}\]

Шаг 5 — первый левый сингулярный вектор.

\[\mathbf{u}_1 = \frac{A\mathbf{v}_1}{\sigma_1} = \frac{1}{\sqrt{14}}\begin{bmatrix} 1 \\ 2 \\ 3 \end{bmatrix}\]

Шаг 6 — дополнить \(U\) до базиса в \(\mathbb{R}^3\).

Например, \[\mathbf{u}_2 = \frac{1}{\sqrt{5}}\begin{bmatrix} -2 \\ 1 \\ 0 \end{bmatrix}, \qquad \mathbf{u}_3 = \frac{1}{\sqrt{70}}\begin{bmatrix} -3 \\ -6 \\ 5 \end{bmatrix}\]

(вместе с \(\mathbf{u}_1\) — ортонормированная тройка).

Шаг 7 — SVD.

\[A = U\Sigma V^T = \begin{bmatrix} \mathbf{u}_1 & \mathbf{u}_2 & \mathbf{u}_3 \end{bmatrix} \begin{bmatrix} \sqrt{70} & 0 \\ 0 & 0 \\ 0 & 0 \end{bmatrix} \begin{bmatrix} \mathbf{v}_1^T \\ \mathbf{v}_2^T \end{bmatrix}\]

Ответ: \(\sigma_1 = \sqrt{70}\), \(\sigma_2 = 0\), \(\text{rank}(A)=1\); усечённое SVD: \(A = \sqrt{70}\,\mathbf{u}_1\mathbf{v}_1^T\).

4.21 Четыре подпространства из SVD (Туториал 8, Пример 4)

У матрицы \(A\) размера \(4 \times 5\) в SVD \(\Sigma = \text{diag}(8, 5, 2, 0)\) (как у матрицы \(4 \times 5\)) и ортонормированные левые сингулярные векторы \(\mathbf{u}_1, \mathbf{u}_2, \mathbf{u}_3, \mathbf{u}_4\), правые \(\mathbf{v}_1, \ldots, \mathbf{v}_5\). Укажите четыре фундаментальных подпространства.

Нажмите, чтобы увидеть решение

Ключевая идея: по SVD и рангу подпространства читаются с сингулярных векторов без дополнительных вычислений.

Шаг 1 — ранг.

На диагонали \((8, 5, 2, 0)\) — три ненулевых значения: \[r = \text{rank}(A) = 3\]

Шаг 2 — подпространства.

\(m = 4\), \(n = 5\).

• \(C(A) \subseteq \mathbb{R}^4\), \(\dim = 3\): \(\text{span}\{\mathbf{u}_1, \mathbf{u}_2, \mathbf{u}_3\}\).
• \(N(A^T) \subseteq \mathbb{R}^4\), \(\dim = 1\): \(\text{span}\{\mathbf{u}_4\}\) (к \(\sigma_4 = 0\)).
• \(C(A^T) \subseteq \mathbb{R}^5\), \(\dim = 3\): \(\text{span}\{\mathbf{v}_1, \mathbf{v}_2, \mathbf{v}_3\}\).
• \(N(A) \subseteq \mathbb{R}^5\), \(\dim = 2\): \(\text{span}\{\mathbf{v}_4, \mathbf{v}_5\}\).

Проверка размерностей: \(3+1=4=m\), \(3+2=5=n\). Ортогональность пар — фундаментальная теорема линейной алгебры.

Ответ: \(C(A) = \text{span}\{\mathbf{u}_1, \mathbf{u}_2, \mathbf{u}_3\}\); \(N(A^T) = \text{span}\{\mathbf{u}_4\}\); \(C(A^T) = \text{span}\{\mathbf{v}_1, \mathbf{v}_2, \mathbf{v}_3\}\); \(N(A) = \text{span}\{\mathbf{v}_4, \mathbf{v}_5\}\).

4.22 SVD как сумма матриц ранга 1 (Туториал 8, Пример 5)

Найдите полное SVD матрицы \(A = \begin{bmatrix} 2 & 0 \\ 0 & 0 \\ 0 & 1 \end{bmatrix}\) и запишите \(A\) как сумму матриц ранга 1.

Нажмите, чтобы увидеть решение

Ключевая идея: имея SVD, разложение \(A = \sum_i \sigma_i \mathbf{u}_i \mathbf{v}_i^T\) получают сразу; сумма восстанавливает \(A\).

Шаг 1 — \(A^TA\).

\[A^TA = \begin{bmatrix} 2 & 0 & 0 \\ 0 & 0 & 1 \end{bmatrix}\begin{bmatrix} 2 & 0 \\ 0 & 0 \\ 0 & 1 \end{bmatrix} = \begin{bmatrix} 4 & 0 \\ 0 & 1 \end{bmatrix}\]

Шаг 2 — собственные значения и сингулярные числа.

\(A^TA = \text{diag}(4, 1)\), значит \(\lambda_1 = 4\), \(\lambda_2 = 1\), \(\sigma_1 = 2\), \(\sigma_2 = 1\), \(\text{rank}(A)=2\).

Шаг 3 — правые сингулярные векторы.

\[\mathbf{v}_1 = \begin{bmatrix} 1 \\ 0 \end{bmatrix}\ (\lambda = 4), \qquad \mathbf{v}_2 = \begin{bmatrix} 0 \\ 1 \end{bmatrix}\ (\lambda = 1), \qquad V = I_2\]

Шаг 4 — левые сингулярные векторы.

\[\mathbf{u}_1 = \begin{bmatrix} 1 \\ 0 \\ 0 \end{bmatrix}, \qquad \mathbf{u}_2 = \begin{bmatrix} 0 \\ 0 \\ 1 \end{bmatrix}\]

Дополнение \(U\) до \(3\times 3\): \(\mathbf{u}_3\) ортогонален \(\mathbf{u}_1\) и \(\mathbf{u}_2\):

\[\mathbf{u}_3 = \begin{bmatrix} 0 \\ 1 \\ 0 \end{bmatrix}, \qquad U = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \end{bmatrix}\]

Шаг 5 — SVD.

\[A = U\Sigma V^T = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \end{bmatrix}\begin{bmatrix} 2 & 0 \\ 0 & 1 \\ 0 & 0 \end{bmatrix}\begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix}\]

Шаг 6 — сумма ранг-1.

\[A = \sigma_1\,\mathbf{u}_1\mathbf{v}_1^T + \sigma_2\,\mathbf{u}_2\mathbf{v}_2^T = 2\begin{bmatrix}1\\0\\0\end{bmatrix}\begin{bmatrix}1&0\end{bmatrix} + \begin{bmatrix}0\\0\\1\end{bmatrix}\begin{bmatrix}0&1\end{bmatrix} = A.\ \checkmark\]

Ответ: \(\sigma_1 = 2\), \(\sigma_2 = 1\); \(A = 2\,\mathbf{u}_1\mathbf{v}_1^T + \mathbf{u}_2\mathbf{v}_2^T\).

4.23 Связь с собственными значениями: \(A^TA = V\Sigma^T\Sigma V^T\) (Туториал 8, Пример 6)

Пусть \(A = U\Sigma V^T\) — SVD. Докажите, что \(A^TA = V\Sigma^T\Sigma V^T\), и выведите, что собственные значения \(A^TA\) равны \(\sigma_i^2\).

Нажмите, чтобы увидеть решение

Ключевая идея: это соединяет SVD со спектральным разложением и объясняет, почему сингулярные числа ищут через \(A^TA\). Используются \((XYZ)^T = Z^TY^TX^T\) и \(U^TU = I\).

Шаг 1 — развернуть \(A^TA\).

\[A^TA = (U\Sigma V^T)^T(U\Sigma V^T)\]

\[(U\Sigma V^T)^T = V\Sigma^T U^T \Rightarrow A^TA = (V\Sigma^T U^T)(U\Sigma V^T)\]

Шаг 2 — упростить.

\[A^TA = V\Sigma^T (U^T U)\Sigma V^T = V(\Sigma^T\Sigma)V^T\]

Шаг 3 — интерпретация.

\(\Sigma^T\Sigma\) — диагональная \(n\times n\) с \(\sigma_1^2, \ldots, \sigma_r^2\) и нулями; \(V(\Sigma^T\Sigma)V^T\) — спектральное разложение \(A^TA\) с ортогональной \(V\).

Итог: собственные значения \(A^TA\) — \(\sigma_i^2 \geq 0\), откуда \(A^TA\) всегда PSD.

Ответ: \(A^TA = V(\Sigma^T\Sigma)V^T\); \(\lambda_i(A^TA) = \sigma_i^2 \geq 0\).

4.24 Сжатие изображения через SVD (Туториал 8, Пример 7)

Полутоновое изображение задано матрицей \(M \in \mathbb{R}^{500 \times 400}\). Пусть \(\text{rank}(M)=400\) (все сингулярные числа ненулевые). (а) Сколько чисел нужно для полной матрицы? (б) Сколько чисел в ранг-3 SVD-приближении? (в) Каков коэффициент сжатия?

Нажмите, чтобы увидеть решение

Ключевая идея: ранг-\(k\) приближение хранит \(k\) левых и \(k\) правых сингулярных векторов плюс \(k\) сингулярных чисел — всего \(k(m+n+1)\) чисел; это часто меньше \(mn\).

Шаг 1 — полная матрица.

\[\text{память}_{\text{полн}} = mn = 500 \times 400 = 200{,}000\ \text{чисел}\]

Шаг 2 — ранг 3.

При \(k = 3\), \(m = 500\), \(n = 400\):

\[\text{память}_{k=3} = k(m + n + 1) = 3 \times 901 = 2{,}703\ \text{числа}\]

в том числе: \(3\) сингулярных числа, \(3 \times 500 = 1{,}500\) координат левых векторов, \(3 \times 400 = 1{,}200\) — правых.

Шаг 3 — коэффициент сжатия.

\[\text{коэффициент} = \frac{2{,}703}{200{,}000} \approx 0{,}0135 \approx 1{,}35\%\]

Визуальное качество зависит от доли энергии в первых трёх сингулярных числах; при сильной низкоранговой структуре картинки приближение может выглядеть приемлемо.

Ответ: (а) \(200{,}000\) чисел; (б) \(2{,}703\); (в) \(\approx 1{,}35\%\) от полной матрицы.